Search for: All records

Abstract Let$$M_{\langle \mathbf {u},\mathbf {v},\mathbf {w}\rangle }\in \mathbb C^{\mathbf {u}\mathbf {v}}{\mathord { \otimes } } \mathbb C^{\mathbf {v}\mathbf {w}}{\mathord { \otimes } } \mathbb C^{\mathbf {w}\mathbf {u}}$$denote the matrix multiplication tensor (and write$$M_{\langle \mathbf {n} \rangle }=M_{\langle \mathbf {n},\mathbf {n},\mathbf {n}\rangle }$$), and let$$\operatorname {det}_3\in (\mathbb C^9)^{{\mathord { \otimes } } 3}$$denote the determinant polynomial considered as a tensor. For a tensorT, let$$\underline {\mathbf {R}}(T)$$denote its border rank. We (i) give the first hand-checkable algebraic proof that$$\underline {\mathbf {R}}(M_{\langle 2\rangle })=7$$, (ii) prove$$\underline {\mathbf {R}}(M_{\langle 223\rangle })=10$$and$$\underline {\mathbf {R}}(M_{\langle 233\rangle })=14$$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was$$M_{\langle 2\rangle }$$, (iii) prove$$\underline {\mathbf {R}}( M_{\langle 3\rangle })\geq 17$$, (iv) prove$$\underline {\mathbf {R}}(\operatorname {det}_3)=17$$, improving the previous lower bound of$$12$$, (v) prove$$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.32\mathbf {n}$$for all$$\mathbf {n}\geq 25$$, where previously only$$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1$$was known, as well as lower bounds for$$4\leq \mathbf {n}\leq 25$$, and (vi) prove$$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.6\mathbf {n}$$for all$$\mathbf {n} \ge 18$$, where previously only$$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+2$$was known. The last two results are significant for two reasons: (i) they are essentially the first nontrivial lower bounds for tensors in an “unbalanced” ambient space and (ii) they demonstrate that the methods we use (border apolarity) may be applied to sequences of tensors. The methods used to obtain the results are new and “nonnatural” in the sense of Razborov and Rudich, in that the results are obtained via an algorithm that cannot be effectively applied to generic tensors. We utilize a new technique, calledborder apolaritydeveloped by Buczyńska and Buczyński in the general context of toric varieties. We apply this technique to develop an algorithm that, given a tensorTand an integerr, in a finite number of steps, either outputs that there is no border rankrdecomposition forTor produces a list of all normalized ideals which could potentially result from a border rank decomposition. The algorithm is effectively implementable whenThas a large symmetry group, in which case it outputs potential decompositions in a natural normal form. The algorithm is based on algebraic geometry and representation theory. 

We prove that the border rank of the Kronecker square of the little Coppersmith–Winograd tensor Tcw,q is the square of its border rank for q > 2 and that the border rank of its Kronecker cube is the cube of its border rank for q > 4. This answers questions raised implicitly by Coppersmith & Winograd (1990, §11) and explicitly by Bl¨aser (2013, Problem 9.8) and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith–Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen’s laser method, introducing a skew-symmetric version of the Coppersmith– Winograd tensor, Tskewcw,q. For q = 2, the Kronecker square of this tensor coincides with the 3 × 3 determinant polynomial, det3 ∈ C9 ⊗ C9 ⊗ C9, regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of det3, exhibiting a strict submultiplicative behaviour for Tskewcw,2 which is promising for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C3 ⊗ C3 ⊗ C3. 

We make a first geometric study of three varieties inCm⊗Cm⊗Cm (for eachm), including the Zariski closure of the set of tight tensors, the tensors with continuous regular symmetry. Our motivation is to develop a geometric framework for Strassen’s asymptotic rank conjecture that the asymptotic rank of any tight tensor is minimal. In particular, we determine the dimension of the set of tight tensors. We prove that this dimension equals the dimension of the set of oblique tensors, a less restrictive class introduced by Strassen. 

We answer a question, posed implicitly in [P. Bürgisser et al., 1997] and explicitly in [M. Bläser, 2013], showing the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of the border rank of the tensor for all q>2, a negative result for complexity theory. We further show that when q>4, the analogous result holds for the Kronecker cube. In the positive direction, we enlarge the list of explicit tensors potentially useful for the laser method. We observe that a well-known tensor, the 3 × 3 determinant polynomial regarded as a tensor, det_3 ∈ C^9 ⊗ C^9 ⊗ C^9, could potentially be used in the laser method to prove the exponent of matrix multiplication is two. Because of this, we prove new upper bounds on its Waring rank and rank (both 18), border rank and Waring border rank (both 17), which, in addition to being promising for the laser method, are of interest in their own right. We discuss "skew" cousins of the little Coppersmith-Winograd tensor and indicate why they may be useful for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C^3 ⊗ C^3 ⊗ C^3.